package huaweiod.second;

import java.util.*;

/**
 * 5G网络建设
 * https://renjie.blog.csdn.net/article/details/135095195
 */
public class C7_5gNetworkConstruct {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();   // 基站个数
        int m = in.nextInt();   // 光纤直连条件个数
        Set<Integer> selectSet = new HashSet<>();     // 已连接的基站节点
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int x = in.nextInt();   // 基站x
            int y = in.nextInt();   // 基站y
            int z = in.nextInt();   // 连接成本
            int p = in.nextInt();   // 0:未连接，1:已连接
            if (p == 1) {
                selectSet.add(x);
                selectSet.add(y);
            } else {
                list.add(new int[]{x, y, z});
            }
        }
        int dfs = dfs(0, list, selectSet, n);
        if (dfs != Integer.MAX_VALUE) {
            System.out.println(dfs);
        } else {
            System.out.println(-1);
        }
    }

    public static int dfs(int cur, List<int[]> list, Set<Integer> selectSet, int n) {
        if (selectSet.size() == n) {
            return 0;
        }
        if (cur == list.size()) {
            return Integer.MAX_VALUE;
        }
        // 不连接
        int p1 = dfs(cur + 1,list,selectSet,n);
        // 连接
        int[] ints = list.get(cur);
        int x = ints[0];
        int y = ints[1];
        int p = ints[2];
        int p2 = Integer.MAX_VALUE;
        if(!selectSet.contains(x) && !selectSet.contains(y)) {
            selectSet.add(x);
            selectSet.add(y);
            int next = dfs(cur + 1,list,selectSet,n);
            if (next != Integer.MAX_VALUE) {
                p2 = p + next;
            }
            selectSet.remove(x);
            selectSet.remove(y);
        }
        if(selectSet.contains(x) && !selectSet.contains(y)) {
            selectSet.add(y);
            int next = dfs(cur + 1,list,selectSet,n);
            if (next != Integer.MAX_VALUE) {
                p2 = p + next;
            }
            selectSet.remove(y);
        }
        if(!selectSet.contains(x) && selectSet.contains(y)) {
            selectSet.add(x);
            int next = dfs(cur + 1,list,selectSet,n);
            if (next != Integer.MAX_VALUE) {
                p2 = p + next;
            }
            selectSet.remove(x);
        }
        return Math.min(p1, p2);
    }
}
